package nr.co.mhgames.polyanim.util;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

import nr.co.mhgames.polyanim.Polygon;

/**
 * Implements a basic triangulator for simple polygons (no holes or
 * self-intersections allowed). This can be optionally used by the LWJGL
 * renderer to enable rendering of concave polygons.
 * <p>
 * The code is based on a class by the same name in Kevin Glass' Slick-library,
 * which in turn is based on public sources. I've just modified it for PolyAnim
 * use and taken out things that we don't need. The original description
 * follows:
 * <p>
 * Triangulates a polygon into triangles - duh. Doesn't handle holes in polys
 * 
 * @author Based on Public Source from FlipCode
 * @author Mika Halttunen
 */
public class BasicTriangulator implements Triangulator {
	/** The accepted error value */
	private static final float EPSILON = 0.0000001f;

	/** The list of triangulated polygons */
	private final List<Polygon> polys;

	/** The list of vertices describing the triangles */
	private final List<Vertex> triangles;

	/** Constructor */
	public BasicTriangulator() {
		polys = new ArrayList<Polygon>();
		triangles = new ArrayList<Vertex>();
	}

	/**
	 * Triangulate the given simple polygon.
	 * 
	 * @param poly
	 *            Polygon to triangulate. Must be simple (no holes or
	 *            self-intersections)
	 * @return List of triangle polygons.
	 */
	public List<Polygon> triangulatePolygon(Polygon poly) {
		polys.clear();

		// Already a triangle?
		if (poly.getVertexCount() <= 3) {
			polys.add(poly);
			return polys;
		}

		// Try to triangulate
		boolean worked = process(poly.getVertices(), triangles);
		if (worked) {
			for (Iterator<Vertex> it = triangles.iterator(); it.hasNext();) {
				Polygon p = new Polygon(poly.getColor());

				// Add the vertices
				p.addVertex(it.next());
				p.addVertex(it.next());
				p.addVertex(it.next());

				// Store the polygon
				polys.add(p);
			}
		}

		return polys;
	}

	/**
	 * Find the area of a polygon defined by the series of points in the list
	 * 
	 * @param contour
	 *            The list of points defined the contour of the polygon
	 *            (Vector2f)
	 * @return The area of the polygon defined
	 */
	private float area(List<Vertex> contour) {
		int n = contour.size();

		float A = 0.0f;

		for (int p = n - 1, q = 0; q < n; p = q++) {
			Vertex contourP = contour.get(p);
			Vertex contourQ = contour.get(q);

			A += contourP.position.x * contourQ.position.y - contourQ.position.x
					* contourP.position.y;
		}

		// MH: As the area is only used for determining the vertex winding, we
		// don't need to exact area
		// return A * 0.5f;

		return A;
	}

	/**
	 * Check if the point P is inside the triangle defined by the points A,B,C
	 * 
	 * @param Ax
	 *            Point A x-coordinate
	 * @param Ay
	 *            Point A y-coordinate
	 * @param Bx
	 *            Point B x-coordinate
	 * @param By
	 *            Point B y-coordinate
	 * @param Cx
	 *            Point C x-coordinate
	 * @param Cy
	 *            Point C y-coordinate
	 * @param Px
	 *            Point P x-coordinate
	 * @param Py
	 *            Point P y-coordinate
	 * @return True if the point specified is within the triangle
	 */
	private boolean insideTriangle(float Ax, float Ay, float Bx, float By, float Cx, float Cy,
			float Px, float Py) {
		float ax, ay, bx, by, cx, cy, apx, apy, bpx, bpy, cpx, cpy;
		float cCROSSap, bCROSScp, aCROSSbp;

		ax = Cx - Bx;
		ay = Cy - By;
		bx = Ax - Cx;
		by = Ay - Cy;
		cx = Bx - Ax;
		cy = By - Ay;
		apx = Px - Ax;
		apy = Py - Ay;
		bpx = Px - Bx;
		bpy = Py - By;
		cpx = Px - Cx;
		cpy = Py - Cy;

		aCROSSbp = ax * bpy - ay * bpx;
		cCROSSap = cx * apy - cy * apx;
		bCROSScp = bx * cpy - by * cpx;

		return ((aCROSSbp >= 0.0f) && (bCROSScp >= 0.0f) && (cCROSSap >= 0.0f));
	}

	/**
	 * Cut a the contour and add a triangle into V to describe the location of
	 * the cut
	 * 
	 * @param contour
	 *            The list of points defining the polygon
	 * @param u
	 *            The index of the first point
	 * @param v
	 *            The index of the second point
	 * @param w
	 *            The index of the third point
	 * @param n
	 *            ?
	 * @param V
	 *            The array to populate with indicies of triangles
	 * @return True if a triangle was found
	 */
	private boolean snip(List<Vertex> contour, int u, int v, int w, int n, int[] V) {
		int p;
		float Ax, Ay, Bx, By, Cx, Cy, Px, Py;

		Ax = contour.get(V[u]).position.x;
		Ay = contour.get(V[u]).position.y;

		Bx = contour.get(V[v]).position.x;
		By = contour.get(V[v]).position.y;

		Cx = contour.get(V[w]).position.x;
		Cy = contour.get(V[w]).position.y;

		if (EPSILON > (((Bx - Ax) * (Cy - Ay)) - ((By - Ay) * (Cx - Ax)))) {
			return false;
		}

		for (p = 0; p < n; ++p) {
			if ((p == u) || (p == v) || (p == w)) {
				continue;
			}

			Px = contour.get(V[p]).position.x;
			Py = contour.get(V[p]).position.y;

			if (insideTriangle(Ax, Ay, Bx, By, Cx, Cy, Px, Py)) {
				return false;
			}
		}

		return true;
	}

	/**
	 * Process a list of points defining a polygon
	 * 
	 * @param contour
	 *            The list of points describing the polygon
	 * @param result
	 *            The list of points describing the triangles. Groups of 3
	 *            describe each triangle
	 * @return True if we succeeded in completing triangulation
	 */
	private boolean process(List<Vertex> contour, List<Vertex> result) {
		result.clear();

		/* allocate and initialize list of Vertices in polygon */

		int n = contour.size();
		if (n < 3)
			return false;

		int[] V = new int[n];

		/* we want a counter-clockwise polygon in V */

		if (0.0f < area(contour)) {
			for (int v = 0; v < n; ++v)
				V[v] = v;
		} else {
			for (int v = 0; v < n; ++v)
				V[v] = (n - 1) - v;
		}

		int nv = n;

		/* remove nv-2 Vertices, creating 1 triangle every time */
		int count = 2 * nv; /* error detection */

		for (int m = 0, v = nv - 1; nv > 2;) {
			/* if we loop, it is probably a non-simple polygon */
			if (0 >= (count--)) {
				// ** Triangulator4: ERROR - probable bad polygon!
				return false;
			}

			/* three consecutive vertices in current polygon, <u,v,w> */
			int u = v;
			if (nv <= u)
				u = 0; /* previous */
			v = u + 1;
			if (nv <= v)
				v = 0; /* new v */
			int w = v + 1;
			if (nv <= w)
				w = 0; /* next */

			if (snip(contour, u, v, w, nv, V)) {
				int a, b, c, s, t;

				/* true names of the vertices */
				a = V[u];
				b = V[v];
				c = V[w];

				/* output Triangle */
				result.add(contour.get(a));
				result.add(contour.get(b));
				result.add(contour.get(c));

				m++;

				/* remove v from remaining polygon */
				for (s = v, t = v + 1; t < nv; ++s, ++t) {
					V[s] = V[t];
				}
				nv--;

				/* resest error detection counter */
				count = 2 * nv;
			}
		}

		return true;
	}
}
